The invention relates generally to technology for electronically securing electronic devices using encryption keys and, more particularly, to systems, devices and methods for securing devices using a physically unclonable function (PUF) circuit(s) to generate encryption keys. As described herein, PUFs are known in the art as circuits, components, processes or other entities capable of generating an output, such as a digital word or a function that is resistant to cloning. For example, a device that has such a PUF circuit embodied therein would be difficult to clone in a manner to generate the same PUF circuit output with another device.
Security in electronic devices has become a major concern of manufacturers and users of such devices. This is particularly true for devices such as computers, personal hand held devices, cellular phones and other devices that contain sensitive information. Developers of electronic devices continuously strive to develop systems and methods that make their products impervious to unauthorized access or use.
At the same time, most all applications have cost limitations that must be taken into account. For example, if a complicated authentication process requiring storage and computing resources were employed on an integrated circuit, the costs incurred may not justify the cost of security accomplished, particularly if the end product were a low cost and mass produced consumer product.
Additionally, the time expended in processing is a concern in many applications. For example, if a fingerprint sensor were employed on a laptop computer, it would need to process computations quickly. Consumers are very particular about convenience of use in any product. So, if a user needs to wait a long period of time for the computer to authenticate the sensor, the product may not be accepted. Moreover, if the user access is a barrier to a time critical operation, such as in a manufacturing process, delayed access resulting from an authentication process could be disastrous. These and other factors are taken into account when designing devices that use such operations.
Many techniques are known for securing electronic devices and applications. Traditionally, in cryptology, at least for the last thirty years or so, RSA (a fanciful acronym derived from the initials of the three developers of the algorithm Ron Rivest, Adi Shamir and Len Adleman of Massachusetts Institute of Technology (MIT)) is an algorithm that is used for what is well known as asymmetric matched key pair encryption, such as public key encryption, and is believed to be secure given sufficiently long keys. Generally, public keys are widely used to encrypt messages and are employed in authentication routines. As is well known in the art of asymmetric matched key pair encryption. Encryption, which may also be used for of authentication requires a private key. As is also well known in the art, decryption may be done utilizing what is known as the public key, distributed in some fashion by the possessor of the private/secret key. In addition encryption may be done using the public key, but decryption may only be done by the possessor of the private/secret key, and not even by other possessors of the public key. Thus, the possessors of the public key may very securely communicate over public communication lines and networks without others being able to decrypt the message. This accepts multiple possessors of the public key being able to decrypt messages encrypted by only the possessor of the private key, which is why the private key is often referred to as an authentication or “signature” key. This algorithm as well as other algorithms and techniques are well known to those skilled in the art, and are widely employed in security and authentication applications. Generally, the following steps can be performed to generate public and private keys:
1. Choose two large prime numbers p and q such that p≠q, randomly and independently of each other.
2. Compute n=pq.
3. Compute the quotient φ(n)=(p−1)(q−1).
4. For the public exponent e choose an integer e>1 that is coprime to φ(n).
I.e., gcd(e,φ(n))=1.
5. Compute the private exponent d such that the congruence relation de≡(mod φ(n)) is satisfied.
The prime numbers can be probabilistically tested for primality. A popular choice for the public exponents is e=216+1=65537. Some applications choose smaller values such as e=3, 5, or instead. This is done in order to make implementations on small devices (e.g., smart cards) easier, i.e. encryption and signature verification are faster. However, choosing small public exponents may lead to greater security risks. Steps 4 and 5 can be performed with the extended Euclidean algorithm; see modular arithmetic. Step 3 may alternatively be implemented as λ(n)=1 cm(p−1,q−1) instead of φ(n)=(p−1)(q−1).
This process of generating encryption keys is a complex and computation heavy process, particularly in routine authentication processes. Also, producing an integrated circuit with advanced security features is expensive using conventional systems and methods. In particular, generating prime numbers is taxing on a system design, requiring processor resources, additional chip space for storage and related circuitry, as well as other resources needed for authentication. Utilizing encryption keys outside an integrated circuit chip, off-chip, is also expensive, requiring additional circuitry and integrated circuit chips. Moreover, performing such processes off-chip is less secure, leaving the authentication process vulnerable to attack.
Also, in practice, conventional authentication processes take time to perform, and often leave a user waiting for the process to complete. For example, in authenticating a typical software application, a user must wait while such a process is completed before access or use is allowed. In many applications, particularly with small electronic devices such as laptop computers, personal data assistants (PDAs), cellular phones, and other devices, this can be burdensome for the device processor as well as for an impatient user. Using the processors and other hardware available in today's small common electronic devices, computing the public and private RSA key pair can take anywhere from 10 to 30 seconds. Even on fast personal computers, times of 1 to 3 seconds are common. Such time delays are undesirable in modern devices.
One approach could be to employ a PUF circuit to more securely provide an output word for use in generating encryption keys. This would eliminate the need for storage of a public or private key on a device. Conventional approaches have addressed such a configuration in prior art publications. One example, U.S. Pat. No. 6,161,213 discloses the use of PUF circuits for component chip identification and other related applications. For example, a PUF circuit could be used to produce a unique word for use in an RSA public/private key generation algorithm so that the component chip always produced the same public/private key pair. There are many problems with this approach. First, consistent production of a number by a PUF circuit is not guaranteed. It is known that uniqueness of a number generated from a PUF circuit in a component chip is possible, but it cannot be produced consistently. In practice, the unique number generated, a digital number, changes upon the excitation of the PUF circuit, and different numbers are produced. As discussed above, using conventional methods, authentication using such means requires significant resources and takes such time and resource consuming processes are not desired in most applications, and are a great impediment to adoption. In addition, using such a number, which practically speaking would be of much smaller size that a prime number typically used in such encryption schemes as RSA, and also without any guarantee that it is a prime number, can significantly reduce the encryption system resistance to unauthorized decryption in the RSA and other such schemes using large prime numbers to generate the encryption keys.
However, conventional technology is not adequate for utilizing such identification. Using conventional methods, the PUF output would be used as a starting point, followed by the application of a complex and very time consuming algorithm to produce the public and private key pairs. Moreover, each time the keys are needed for authentication, the algorithm would need to be repeated, again needing to repeat the same complex and resource consuming algorithm to produce generate the large prime numbers needed for producing the public and private keys. Also, for security reasons, it is not desired to store the key pairs in non-volatile memory. Indeed, the purpose of having a PUF circuit is to eliminate the storage of unique numbers that can be read easily by an intruder trying to bypass or otherwise fool the authentication process. Thus, in a consumer application, if a fingerprint sensor for example, if the delays had to occur upon each authentication, consumer product manufacturers would be reluctant to adopt such a system. Consumers would simply not tolerate such delays. Faster and more convenient systems would be much more easily adopted and accepted.
Thus, there exists a great need in the art for a more efficient means to accurately and efficiently produce asymmetric paired keys, such as RSA keys for component chip and related devices, particularly to avoid the conventional complex and time consuming process used in prior art systems and processes for generating security keys each time a device needs to be authenticated. The need must address the tradeoffs such as the level of security provided, the related cost of manufacture and the resulting speed of operation. As will be seen, the invention provides a means to overcome the shortcomings of conventional systems in an elegant manner.